package leetcode.datastruct1;

import java.util.ArrayList;
import java.util.List;

/**
 * 中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
 *
 * 例如 arr = [2,3,4] 的中位数是 3 。
 * 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
 * 实现 MedianFinder 类:
 *
 * MedianFinder() 初始化 MedianFinder 对象。
 *
 * void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
 *
 * double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。
 *
 * 示例 1：
 *
 * 输入
 * ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
 * [[], [1], [2], [], [3], []]
 * 输出
 * [null, null, null, 1.5, null, 2.0]
 *
 * 解释
 * MedianFinder medianFinder = new MedianFinder();
 * medianFinder.addNum(1);    // arr = [1]
 * medianFinder.addNum(2);    // arr = [1, 2]
 * medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
 * medianFinder.addNum(3);    // arr[1, 2, 3]
 * medianFinder.findMedian(); // return 2.0
 * 提示:
 *
 * -105 <= num <= 105
 * 在调用 findMedian 之前，数据结构中至少有一个元素
 * 最多 5 * 104 次调用 addNum 和 findMedian
 */
public class LeetCode295_MedianFinder {

    private List<Integer> big = new ArrayList<>();
    private List<Integer> small = new ArrayList<>();

    /**
     * 大根堆 + 小根堆
     * 大根堆代表 小于 中位数的部分
     * 小根堆代表 大于 中位数的部分
     * 由于需要保证两个堆的数量差值不能大于1，并且大于中位数和小于中位数的值分布到两个堆中，需要在在加入堆中时进行调整
     * 假设，开始默认加入的堆是大根堆，当加入第二个数时大堆与小堆的数量差值为1，
     * 因此必须要有数加入小堆，但是需要加入的是两个值中较大的值，因为小堆中的值大于大堆中的值
     * 反之，在小堆中数量中多时，也要进行进行调整。
     *
     */
    public LeetCode295_MedianFinder() {

    }

    public void addNum(int num) {
        if (big.isEmpty()) {
            addBig(num);
            return;
        }
        // 加入堆
        if (num > bigHead()) {
            addSmall(num);
        }else {
            addBig(num);
        }

        // 调整堆大小
        if (big.size() - small.size() > 1) {
            addSmall(bigPopBanlance());
        }
        if (small.size() - big.size() > 1) {
            addBig(smallPopBanlance());
        }
    }

    public double findMedian() {
        if (big.size() == small.size()) {
            return (big.get(0) + small.get(0)) / 2.0;
        }
        return big.size() > small.size() ? big.get(0) : small.get(0);
    }

    public void addSmall(int num) {
        small.add(num);
        int curIndex = small.size() - 1;
        int compareIndex, tempV;
        while (curIndex > 0) {
            compareIndex = (curIndex - 1) / 2;
            // 交换
            if (small.get(compareIndex) > small.get(curIndex)) {
                tempV = small.get(compareIndex);
                small.set(compareIndex, small.get(curIndex));
                small.set(curIndex, tempV);
                curIndex = compareIndex;
            }else {
                break;
            }
        }
    }

    public void addBig(int num) {
        big.add(num);
        int curIndex = big.size() - 1;
        int compareIndex, tempV;
        while (curIndex > 0) {
            compareIndex = (curIndex - 1) / 2;
            // 交换
            if (big.get(compareIndex) < big.get(curIndex)) {
                tempV = big.get(compareIndex);
                big.set(compareIndex, big.get(curIndex));
                big.set(curIndex, tempV);
                curIndex = compareIndex;
            }else {
                break;
            }
        }
    }

    public int bigHead() {
        return big.get(0);
    }

    /**
     * 弹出第一个，并调整
     * 第一个弹出后，最后一个补上来，再调整
     */
    public int bigPopBanlance() {
        int r = big.get(0);
        if (big.size() == 1) {
            big.remove(0);
            return r;
        }
        big.set(0, big.get(big.size() - 1));
        big.remove(big.size() - 1);

        // 从根开始向下调整
        int curIndex = 0, tempIndex = 0, tempV;
        int left = curIndex * 2 + 1;
        int right = curIndex * 2 + 2;
        // 存在左右节点
        while (left <= big.size() - 1 && right <= big.size() - 1) {
            // 停止调整
            if (big.get(curIndex) >= big.get(left) &&
                    big.get(curIndex) >= big.get(right)
            ) {
                return r;
            }
            // 交换值
            tempIndex = big.get(left) >= big.get(right) ? left : right;
            tempV = big.get(tempIndex);
            big.set(tempIndex, big.get(curIndex));
            big.set(curIndex, tempV);
            curIndex = tempIndex;

            left = curIndex * 2 + 1;
            right = curIndex * 2 + 2;
        }
        // 无左右节点
        if (left > big.size() - 1 && right > big.size() - 1) {
            return r;
        }
        // 只有左节点，不可能只有右节点没有左节点
        if (left == big.size() - 1) {
            if (big.get(curIndex) < big.get(left)) {
                tempV = big.get(left);
                big.set(left, big.get(curIndex));
                big.set(curIndex, tempV);
            }
        }
        return r;
    }

    /**
     *
     */
    public int smallPopBanlance() {
        int r = small.get(0);
        if (small.size() == 1) {
            small.remove(0);
            return r;
        }
        small.set(0, small.get(small.size() - 1));
        small.remove(small.size() - 1);

        // 从根开始向下调整
        int curIndex = 0, tempIndex = 0, tempV;
        int left = curIndex * 2 + 1;
        int right = curIndex * 2 + 2;
        // 存在左右节点
        while (left <= small.size() - 1 && right <= small.size() - 1) {
            // 停止调整
            if (small.get(curIndex) <= small.get(left) &&
                    small.get(curIndex) <= small.get(right)
            ) {
                return r;
            }
            // 交换值
            tempIndex = small.get(left) <= small.get(right) ? left : right;
            tempV = small.get(tempIndex);
            small.set(tempIndex, small.get(curIndex));
            small.set(curIndex, tempV);
            curIndex = tempIndex;

            left = curIndex * 2 + 1;
            right = curIndex * 2 + 2;
        }
        // 无左右节点
        if (left > small.size() - 1 && right > small.size() - 1) {
            return r;
        }
        // 只有左节点，不可能只有右节点没有左节点
        if (left == small.size() - 1) {
            if (small.get(curIndex) > small.get(left)) {
                tempV = small.get(left);
                small.set(left, small.get(curIndex));
                small.set(curIndex, tempV);
            }
        }
        return r;
    }

    public static void main(String[] args) {
        LeetCode295_MedianFinder leetCode295MedianFinder = new LeetCode295_MedianFinder();
        leetCode295MedianFinder.addNum(6);
        leetCode295MedianFinder.addNum(10);
        leetCode295MedianFinder.addNum(2);
        leetCode295MedianFinder.addNum(6);
        leetCode295MedianFinder.addNum(5);
        leetCode295MedianFinder.addNum(0);
        leetCode295MedianFinder.addNum(6);
        leetCode295MedianFinder.addNum(3);
        leetCode295MedianFinder.addNum(1);
        leetCode295MedianFinder.addNum(0);
        leetCode295MedianFinder.addNum(0);

//        leetCode295MedianFinder.addBig(1);
//        leetCode295MedianFinder.addBig(2);
//        leetCode295MedianFinder.addBig(3);
//        leetCode295MedianFinder.addBig(4);
//        leetCode295MedianFinder.addBig(5);
//
//        System.out.println("leetCode295MedianFinder.bigPopBanlance() = " + leetCode295MedianFinder.bigPopBanlance());
//        System.out.println("leetCode295MedianFinder.bigPopBanlance() = " + leetCode295MedianFinder.bigPopBanlance());
//        System.out.println("leetCode295MedianFinder.bigPopBanlance() = " + leetCode295MedianFinder.bigPopBanlance());
//        System.out.println("leetCode295MedianFinder.bigPopBanlance() = " + leetCode295MedianFinder.bigPopBanlance());

//        leetCode295MedianFinder.addSmall(1);
//        leetCode295MedianFinder.addSmall(2);
//        leetCode295MedianFinder.addSmall(3);
//        leetCode295MedianFinder.addSmall(4);
//        leetCode295MedianFinder.addSmall(5);
//
//        System.out.println("leetCode295MedianFinder.smallPopBanlance() = " + leetCode295MedianFinder.smallPopBanlance());
//        System.out.println("leetCode295MedianFinder.smallPopBanlance() = " + leetCode295MedianFinder.smallPopBanlance());
//        System.out.println("leetCode295MedianFinder.smallPopBanlance() = " + leetCode295MedianFinder.smallPopBanlance());
//        System.out.println("leetCode295MedianFinder.smallPopBanlance() = " + leetCode295MedianFinder.smallPopBanlance());
    }
}
